iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 16
1
Security

無趣的密碼學,有趣的加密!系列 第 16

[Day 16] 016 - 橢圓曲線密碼學 - Elliptic Curve Cryptograph (一)

  • 分享至 

  • xImage
  •  

橢圓曲線密碼學 - Elliptic Curve Cryptograph (一)

恩……我不知道大家有沒有學過或知道橢圓曲線。

但如果是我這樣的學渣來說,肯定是不知道這東西的。

當初是因為在學習Diffie–Hellman的時候得知了這東西。

然後也知道了X25519。


橢圓曲線

我們先來說說橢圓曲線的一些特性跟公式:

  1. 橢圓曲線方程式:y^2=x^3+ax+b
  2. 對稱x軸。
  3. a跟b必需要符合:4*a^3 + 27*b^2 != 0,才不會重根。
  4. 橢圓曲線會符合圖片上的條件:

    圖片來自橢圓曲線 WiKi
  5. 這邊要注意的是當曲線在A的切點上時,為2A。

大概知道橢圓曲線的特性之後,我們來整理一下一些結論。

  1. 非垂直的線,穿過曲線後最多只會有3個點。
  2. 任意一個點都可以用x來反射出相反的點。
  3. 挑選曲線上的A點跟B點可以得到C點反射出-C點。
  4. 可以不斷的畫出新的點,並反射出新的點,並連接後得到新的交點。

    圖片來自ECC (Elliptic Curve Cryptosystem)

有限域

這個名詞我知道看到的人都很慌張,但其實就是將數學的結果規定在一個定義域裡,因為一般不會直接使用整個實數域。

在我們使用橢圓曲線時,使用『質數』來做有限域。

這樣做之後,會使曲線變成一堆離散的點,而不會有連續的圖。

其公式就會變成:y^2=x^3+ax+b (mod r)

我知道這很抽象,但實際上就是這樣,看一下圖。

圖片由Elliptic Curves over Finite Fields程式生成。

整個離散且隨機分佈化。

橢圓曲線的計算

這邊要進入到數學的部分了,也就是接下來DH會用到的部分。

橢圓曲線 WiKi裡面其實有寫。

但我還是拿出來講:

  1. 先記得曲線公式:y^2=x^3+ax+b (mod K)。
    • 設定了一個有限域K。
  2. 設點P(Xp,Yp)和Q(Xq,Yq)。
  3. 假設Xp != Xq,設S為(Yp-Yq)/(Xp-Xq) (mod K)。
  4. 假設Xp == Xq,設S為(3*Xp^2 - a)/(2*Yp) (mod K)。
    聰明的大家應該知道,3跟4其實就是取斜率。
  5. 設R=P+Q。
  6. 接下來是一堆數學證明後,我們取得一個結果(證明去Wiki看)。
  7. Xr = S^2 - Xp - Xq (mod K)
  8. Yr = -Yp + S*(Xp - Xr) (mod K)

好的,我們有了上面的公式之後,我們設定一個起始點為G。
直時我們就能從這個起始點得到R設定為2G。
再從G跟2G得到下一個R稱為3G。
不斷的這樣堆疊稱為xG。

一樣我們先手算一下

我設定a=1,b=-1,K=23
選定G(9,1)
Xp == Xq因此:
S = (3*Xp^2 - a)/(2*Yp) (mod K) = 1
Xr = 1^2 - 1 - 1 = -1
Yr = -11 + 1*(1 - (-1)) = -9
R = (18,14)

橢圓曲線的困難

大家可能會問,那這有什麼困難的地方使得整個加密比質因數分解還難。

那就是G這個東西了,大家應該知道xG就是指:x次的G。

有了G跟xG之後,要反推回x次是十分困難的問題。

並且因為具有阿貝爾群因此可以符合交換率。

所以我有個A次跟B次,生成出來的AG跟BG這兩個。

當我把G跟AG、BG當成公鑰,兩方交換後再也去做BAG跟BAG結果會是相同的。

但中間攻擊的人沒辦法把『AG拆解成G跟A』或是『BG拆解G跟B』。

同時無法把AG跟BG做組合,這也就類似於質因數分解。

橢圓曲線的優勢

這就很有意思了~

我列舉一些優點:

  1. 抗攻擊強。
  2. 資源佔用少。
  3. 加解密速度快。
  4. 金鑰很短,卻能提供RSA與之相對的安全性。

而且ECC金鑰長度以線性方式增加,但安全度卻以指數增加,這是多麼優秀的一種方式。

例如:

  • 加密128位的安全加密需要:256位的ECC金鑰 同等於 3072位的RSA金鑰。
  • 加密128位的安全加密需要:512位的ECC金鑰 同等於 15360位的RSA金鑰。

雖然Wiki上面寫的是,目前的估算認為:

破解256位素數域上的橢圓曲線,需要2330個量子比特與1260億個托佛利門。
使用秀爾算法破解2048位的RSA則需要4098個量子比特與5.2萬億個托佛利門。

上述一段為Wiki橢圓曲線迪菲-赫爾曼金鑰交換所描述。

但不管怎麼樣,ECC在目前也是主流中的主流了,後量子密碼學也有橢圓曲線的蹤跡,但那就事後話了。


橢圓曲線結論

這一章看起來短短的,但其實很難。

不只不好理解之外,同時這樣的特性跟曲線也是第一次遇到。

我光把這篇文章搞懂就花了不少的時間。

我在寫程式的時候也有發現到一些問題。

接下來我會花時間來探討如何實做這部份,同時把我找到的資料分享出來。


參考資料

橢圓曲線 WiKi

橢圓曲線加密演算法

橢圓曲線密碼學

橢圓曲線迪菲-赫爾曼金鑰交換

Elliptic Curves over Finite Fields

ECC (Elliptic Curve Cryptosystem)

公钥加密算法那些事 | RSA 与 ECC 系统对比

椭圆曲线加密算法(ECC)


補充資料

Elliptic Curve Cryptography Overview Youtube


上一篇
[Day 15] 015 - 非對稱式密碼學 - Asymmetric cryptography (二)(下)
下一篇
[Day 17] 017 - 橢圓曲線密碼學 - Elliptic Curve Cryptograph (二)
系列文
無趣的密碼學,有趣的加密!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言